package com.zsrt.day20170401;

import com.zsrt.utils.ArrayUtil;

public class SortTest {
	static int a[]=new int[]{2,1,8,3,6,4,9};
	public static void main(String[] args) {
		SortTest st=new SortTest();
		//st.bubbleSort(a);
		//st.selectSort(a);
		//st.insertSort(a);
		//st.quickSort(a, 0, a.length-1);
		//st.bubbleSort1(a);
		//st.heapSort(a);
		st.shellSort(a, a.length);
		ArrayUtil.printArray(a);
		
	}
	
	public void swap(int a[],int x,int y){
		int temp=a[x];
		a[x]=a[y];
		a[y]=temp;
	} 
	
	public  void p(int a[]){
		for(int aa:a){
			System.out.print("  "+aa+"  ");
		}
	}
	
	/*public void bubbleSort(int a[]){
		for(int i=0;i<a.length;i++){
			for(int j=0;j<a.length-i-1;j++){
				if(a[j+1]<a[j])swap(a,j,j+1);
			}
		}
	}*/
	
	/*public void selectSort(int a[]){
		for(int i=0;i<a.length;i++){
			int max=0;
			for(int j=1;j<a.length-i;j++){
				if(a[max]<a[j])max=j;
			}
			if(max!=(a.length-i-1))swap(a,max,a.length-i-1);
		}
	}*/
	
	public void bubbleSort(int a[]){
		for(int i=0;i<a.length;i++){
			for(int j=0;j<a.length-i-1;j++){
				if(a[j+1]<a[j])swap(a,j,j+1);
			}
		}
	}
	
	public void bubbleSort1(int a[]){
		for(int i=1;i<=a.length;i++){
			for(int j=0;j<a.length-i-1;j++){
				if(a[j+1]<a[j])swap(a,j,j+1);
			}
		}
	}
	
	public void selectSort(int a[]){
		for(int i=0;i<a.length;i++){
			int max=0;
			for(int j=1;j<a.length-i;j++){
				if(a[max]<a[j])max=j;
			}
			if(max!=a.length-i-1)swap(a,max,a.length-i-1);
		}
	}
	
	/*public void insertSort(int a[]){
		for(int i=1;i<a.length;i++){
			int temp=a[i];
			int j=i-1;
			while(j>=0&&temp<a[j]){
				a[j+1]=a[j];
				j--;
			}
			a[j+1]=temp;
		}
	}*/
	
	
	
	public void quickSort(int a[],int low,int high){
		if(low<high){
			int middle=getMiddle(a,low,high);
			quickSort(a,low,middle-1);
			quickSort(a,middle+1,high);
		}
		
	}
	
	public int getMiddle(int a[],int low,int high){
		int pivot=a[low];
		while(low<high){
			while(low<high&&pivot<a[high]){
				high--;
			}
			a[low]=a[high];
			while(low<high&&a[low]<pivot){
				low++;
			}
			a[high]=a[low];
		}
		a[low]=pivot;
		return low;
	}
	/**
	 * 堆排序
	 * @param a
	 */
	public void heapSort(int[] a){
		for(int i=0;i<a.length;i++){
			getMaxHeap(a,a.length-i);
			swap(a,0,a.length-i-1);
		}
		
	}
	public void getMaxHeap(int[] a,int size){
		int index=size/2;
		for(int i=index;i>=0;i--){
			getMax(a,i,size);
		}	
	}
	
	public void getMax(int a[],int index,int size){
		int leftChild=2*index+1;
		int rightChild=2*index+2;
		if(leftChild<size&&a[index]<a[leftChild]){
			ArrayUtil.swap(a,index,leftChild);
		}
		if(rightChild<size&&a[index]<a[rightChild]){
			ArrayUtil.swap(a,index,rightChild);
		}
	}
	//希尔排序
	public void shellSort(int[] a,int size){
		
		for(int step=size/2;step>0;step/=2){
			for(int i=step;i<size;i++){
				int temp=a[i];
				int j;
				for(j=i-step;j>=step&&a[j]>temp;j-=step){
					a[j+step]=a[j];
				}
				a[j+step]=temp;
			}
		}
	}
	
	public void insertSort(int[] a){
		for(int i=1;i<a.length;i++){
			int temp=a[i];
			int j=i-1;
			for(;j>=0&&temp<a[j];j--){
				a[j+1]=a[j];
			}
			/*while(j>=0&&temp<a[j]){
				a[j+1]=a[j];
				j--;
			}*/
			a[j+1]=temp;
		}
	}
	

	
	
	
	
	
	
	
	
}
